<TeXmacs|1.99.16>

<project|rehash.tm>

<style|generic>

<\body>
  <section|What is Rehash?><label|what-rehash>

  On an abstract level, Rehash is a decentralised database that maps hashes
  generated by one hash function to hashes generated by another, on the same
  input. More concretely, the GNUnet DHT is used for searching peers that
  have a mapping. As an implementation detail, Rehash is implemented as a
  service implemented in C, with Scheme bindings and a REST API.

  <\definition>
    In Rehash, a hash function <math|f:\<Sigma\><rsub|a><rsup|\<ast\>>\<rightarrow\>\<Sigma\><rsub|b><rsup|n>>
    is a function from finite strings in some finite alphabet
    <math|\<Sigma\><rsub|a>> to fixed-length strings
    <math|\<Sigma\><rsub|b><rsup|n>> in a finite alphabet
    <math|\<Sigma\><rsub|b>> of length <math|n\<in\>\<bbb-N\>>. While such a
    function cannot be injective (assuming
    <math|\<Sigma\><rsub|a>\<neq\>\<emptyset\>>), of a good hash functions is
    expected no collisions are found in practice.<label|rehash-hash-definition>
  </definition>

  <\remark>
    In practice, <math|\<Sigma\><rsub|a>=\<Sigma\><rsub|b>=<around*|{|0,1|}>>
    and <math|n> is a multiple of <math|8>. Alternatively,
    <math|\<Sigma\><rsub|a>=\<Sigma\><rsub|b>=<around*|{|n\<in\>\<bbb-N\><mid|\|>n\<less\>2<rsup|8>|}>>
    and no restrictions are placed on <math|n\<in\>\<bbb-N\>>. Define
    <math|\<Sigma\><rsub|m>=<around*|{|n\<in\>\<bbb-N\><mid|\|>n\<less\>m|}>>.<label|rehash-hash-alphabet>
  </remark>

  <\notation>
    In this document, hash functions are written as <math|f>, <math|g>,
    <math|h>, <text-dots>, inputs to hash functions as
    <math|\<kappa\>,\<lambda\>,\<mu\>>, <text-dots> and outputs of hash
    functions as <math|K=f <around*|(|\<kappa\>|)>>, <math|L=g
    <around*|(|\<lambda\>|)>>, <math|M=h <around*|(|\<mu\>|)>>.<label|rehash-hash-notation>
  </notation>

  <\definition>
    Let <math|f> and <math|g> be two hash functions with the same input
    alphabet. Then an ordered tuple <math|<around*|(|K,L|)>> is said to be a
    <math|<around*|(|f,g|)>>-hash mapping if and only if the intersection of
    the preimage <math|f<rsup|-1> <around*|(|<around*|{|K|}>|)>> of
    <math|<around*|{|K|}>> under <math|f> and the preimage <math|g<rsup|-1>
    <around*|(|<around*|{|L|}>|)>> of <math|<around*|{|L|}>> under <math|g>
    is non-empty. Or equivalently, there exists an input <math|\<kappa\>> of
    <math|f> and <math|g> such that <math|K=f <around*|(|\<kappa\>|)>> and
    <math|L=g <around*|(|\<kappa\>|)>>.<label|rehash-hash-mapping>
  </definition>

  <\lemma>
    <math|<around*|(|K,L|)>> is a <math|<around*|(|f,g|)>>-hash mapping if
    and only if <math|<around*|(|L,K|)>> is a <math|<around*|(|g,f|)>> hash
    mapping.<label|rehash-mapping-symmetry>
  </lemma>

  <\warning>
    The is-a-hash-mapping relationship is not transitive, except for the
    trivial empty input alphabet, because hash functions with non-trivial
    alphabets are not injective.<label|rehash-mapping-intransitive>
  </warning>

  In Table <reference|hashtable>, some hash functions have a number assigned.
  <todo|A GANA registry should be created>

  <\definition>
    Let <math|\<eta\><rsub|h> <around*|(|f|)>> be the numerical identifier of
    <math|f> according to Table <reference|rehash-hashfunction-table>.<label|rehash-numeric-id>
  </definition>

  <\big-table|<tabular|<tformat|<cwith|1|-1|1|1|cell-halign|r>|<cwith|1|1|1|-1|cell-tborder|0ln>|<cwith|1|1|1|-1|cell-bborder|1ln>|<cwith|2|2|1|-1|cell-tborder|1ln>|<cwith|1|1|1|1|cell-lborder|0ln>|<cwith|1|1|3|3|cell-rborder|0ln>|<table|<row|<cell|number>|<cell|name>|<cell|definition>>|<row|<cell|1>|<cell|SHA-256>|<cell|<todo|??>>>|<row|<cell|2>|<cell|SHA-512>|<cell|<todo|??>>>|<row|<cell|3>|<cell|SHA3-256>|<cell|<todo|??>>>|<row|<cell|4>|<cell|SHA3-12>|<cell|<todo|??>>>|<row|<cell|5>|<cell|BLAKE2S-256>|<cell|<todo|??>>>|<row|<cell|6>|<cell|??>|<cell|<todo|??>>>>>>>
    <label|rehash-hashfunction-table>Numerical identifiers of hash functions
  </big-table>

  <section|Rehash and GNUnet><label|rehash-and-gnunet>

  To find hashes in the DHT, a request for a hash and responses must first
  have some binary encoding. To prevent nefarious actors from finding
  interesting hash mappings, answers are encrypted with a key derived from
  the request.

  <subsection|Encoding of hash mappings in the
  DHT><label|rehash-dht-encoding>

  <\definition>
    A hash request <math|R <around*|(|f,g,K|)>> consists of two hash function
    <math|f:\<Sigma\><rsub|a><rsup|\<ast\>>\<rightarrow\>\<Sigma\><rsub|b><rsup|n>>,
    <math|g:\<Sigma\><rsub|a><rsup|\<ast\>>\<rightarrow\>\<Sigma\><rsub|c><rsup|m>>
    and a string <math|K\<in\>\<Sigma\><rsub|b><rsup|n>>. <math|k> is called
    the input hash function, <math|v> the output hash function and
    <math|K\<in\>\<Sigma\><rsub|b><rsup|n>> the input hash. If an input
    <math|\<kappa\>\<in\>f<rsup|-1> <around*|(|<around*|{|K|}>|)>> is found,
    then <math|\<kappa\>> may be called a value of <math|R> and <math|g
    <around*|(|\<kappa\>|)>> an output hash of
    <math|R>.<label|rehash-request-encoding>
  </definition>

  <\notation>
    Let <math|x\|y> denote the concatenation of two strings <math|x> and
    <math|y>.<label|rehash-concatenation-notation>
  </notation>

  <\notation>
    Let <math|\<Eta\>:\<Sigma\><rsub|2<rsup|8>><rsup|\<ast\>>\<rightarrow\>\<Sigma\><rsub|2<rsup|8>><rsup|64>>
    be the hash function implemented by <samp|GNUNET_CRYPTO_hash>,

    <math|\<Kappa\>:\<Sigma\><rsub|2<rsup|8>><rsup|64>\<rightarrow\>KEY> the
    function implemented by <samp|GNUNET_CRYPTO_hash_to_aes_key> and
    <math|\<Epsilon\><rsub|k>:<big|cup><rsub|n\<in\>\<bbb-N\>><around*|\<nobracket\>|\<Sigma\><rsub|2<rsup|8>><rsup|n>\<rightarrow\>\<Sigma\><rsub|2<rsup|8>><rsup|n>|\<nobracket\>>>
    the function implemented by <samp|GNUNET_CRYPTO_symmetric_encrypt> with
    <math|k\<in\>KEY>.<label|gnunet-cryptohash-notation>
  </notation>

  <\notation>
    Let <math|\<beta\><rsub|32> <around*|(|x|)>> be the network-byte-order
    encoding of <math|x\<in\>\<Sigma\><rsub|2<rsup|32>>>.<label|u32-nbo-notation>
  </notation>

  <\convention>
    As encoding the hash function itself is rather unwieldly, a numerical
    identifier from Table <reference|rehash-hashfunction-table> is sent
    instead. The binary encoding <math|o<rsub|r> <around*|(|R|)>> of a hash
    request <math|R <around*|(|k,v,K|)>> is defined as:

    <\equation*>
      o<rsub|r> <around*|(|R|)>=<around*|(|\<beta\><rsub|32>\<circ\>\<eta\><rsub|h>|)>
      <around*|(|f|)>\|<around*|(|\<beta\><rsub|32>\<circ\>\<eta\><rsub|h>|)>
      <around*|(|g|)>\|K
    </equation*>

    The DHT key sent over the network is <math|<around*|(|\<Eta\><rsup|2>\<circ\>o<rsub|r>|)>
    <around*|(|R|)>> and is called the obfuscated query. The encryption key
    for the DHT value is derived from <math|<around*|(|\<Eta\>\<circ\>o<rsub|r>|)>
    <around*|(|R|)>>.
  </convention>

  <\definition>
    The answer to a hash request <math|R <around*|(|f,g,K|)>> is an output
    hash <math|L> of <math|g>. This answer is valid if and only if
    <math|<around*|(|K,L|)>> is a <math|<around*|(|f,g|)>>-hash mapping.
  </definition>

  <\convention>
    The answer <math|L> to a hash request <math|R <around*|(|f,g,K|)>> is
    encoded as <math|L> itself. The DHT value is

    <\equation*>
      o<rsub|d v> <around*|(|R,L|)>=\<Epsilon\><rsub|<around*|(|\<Kappa\>\<circ\>\<Eta\>\<circ\>o<rsub|r>|)>
      <around*|(|R|)>> <around*|(|L|)>
    </equation*>
  </convention>

  <\warning>
    It has not been verified whether the cryptography is sound!
  </warning>

  <subsection|Caching and content pushing><label|rehash-content-pushing>

  <todo|write>

  <subsection|(In-)validation><label|rehash-invalidation>

  <todo|write>

  <subsection|Communication between the rehash service and
  clients><label|rehash-service-client>

  <todo|write>

  <section|Rehash and GNU Guix><label|rehash-and-guix>

  Once all pieces are in place, rehash can be used in GNU Guix

  <subsection|The transparent rehash mirror><label|rehash-the-mirror>

  <todo|this is not actually implemented yet. Details can change>

  The rehash mirror is a content-addressed mirror that can be used by GNU
  Guix (and Nix as well perhaps). It does not serve any narinfos, rather it
  is only a content-addressed mirror. When a substitute is requested through
  the mirror, rehash-mirror will ask the DHT for a corresponding GNUnet FS
  URI and download from there instead. If not found, rehash-mirror will
  download the substitute over a classical mirror, and index the downloaded
  substitute into the GNUnet file-sharing system and insert the mapping into
  rehash.

  <todo|Finding a mapping can be slow. Perhaps allow a timeout, and
  pessimistically ask a classical substitute server in parallel? Some changes
  to <samp|(guix download)> and <samp|(guix scripts substitute)> may be
  necessary for efficiency, though not GNUnet-specific. Perhaps the IPFS
  patch addresses the issue.>

  <subsection|Not-so transparent Guix-Rehash integration>

  <todo|not implemented yet, and not worked out>

  <todo|guix build download? guix scripts substitute? Proper progress
  reporting? guix build?>

  <subsection|A path not taken: embedding the GNUnet hash in the
  narinfo><label|rehash-and-narinfo>

  This is the approach of the <samp|wip-ipfs-substitutes><\footnote>
    <hlink|https://issues.guix.gnu.org/33899|>
  </footnote> patch takes. However, GNUnet isn't quite stable yet, so it
  seems unreasonable for the upstream substitute servers to include GNUnet
  hashes anytime soon. If GNUnet (or at least its file-sharing protocols) is
  stable enough, this will probably be implemented, to avoid bad mappings.

  <\note>
    Generating GNUnet hashes doesn't quite require the full stack, and could
    be done fully in Scheme without too much trouble. See
    <hlink|https://notabug.org/mdevos/scheme-gnunet|> for a suspended
    work-in-progress.
  </note>

  <subsection|Another path not taken: embedding the GNUnet hash in the origin
  specification><label|rehash-and-origin>

  This allows for downloading the source code of a package via GNUnet,
  without an unreliable hash mapping lookup over rehash. However, Guix
  upstream is likely reluctant to add this information to all packages (this
  process can be automated), as GNUnet isn't exactly stable yet, and it isn't
  implausible the file-sharing format will change.
</body>

<\initial>
  <\collection>
    <associate|chapter-nr|1>
    <associate|page-first|?>
    <associate|preamble|false>
    <associate|save-aux|false>
    <associate|section-nr|0>
    <associate|subsection-nr|0>
  </collection>
</initial>